import { swap, testSort, cbtPrint } from "hy-algokit";

export default function heapSort(arr: number[]): number[] {
  const n = arr.length;
  const start = Math.floor(n / 2) - 1; // 最后一个非叶子节点的索引
  for (let i = start; i >= 0; i--) {
    heapifyDown(arr, n, i);
  }

  for (let i = n - 1; i > 0; i--) {
    swap(arr, 0, i);
    heapifyDown(arr, i, 0);
  }

  return arr;
}

// 函数：堆化下移
// 参数：arr：数组，n：数组长度，index：当前节点索引
function heapifyDown(arr: number[], n: number, index: number) {
  // 初始化当前节点索引为传入的索引
  let start = index;
  // 当当前节点索引的左子节点索引小于数组长度时，继续循环
  while (2 * start + 1 < n) {
    // 计算当前节点的左子节点索引
    const childIndexLeft = start * 2 + 1;
    // 计算当前节点的右子节点索引
    const childIndexRight = childIndexLeft + 1;
    // 初始化较大的子节点索引为左子节点索引
    let largerIndex = childIndexLeft;
    // 如果右子节点索引小于数组长度且右子节点的值大于左子节点的值，则将较大的子节点索引更新为右子节点索引
    if (childIndexRight < n && arr[childIndexLeft] <= arr[childIndexRight]) {
      largerIndex = childIndexRight;
    }

    // 如果当前节点的值大于等于较大的子节点的值，则跳出循环
    if (arr[start] >= arr[largerIndex]) {
      break;
    }

    // 交换当前节点和较大的子节点的值
    swap(arr, start, largerIndex);
    // 更新当前节点索引为较大的子节点索引
    start = largerIndex;
  }
}

testSort(heapSort);
